package binary_tree.Leetcode;

import javax.sound.midi.Soundbank;
import java.util.Scanner;

/**
 * 根据前序遍历结果构建二叉树
 */
public class NowVoder_KY11 {
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        private static int index = 0;

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            //多组输入
            while (scanner.hasNext()) {
                //每次读取一行前序遍历的结果
                String str = scanner.next();
                //根据前遍历结果构建二叉树
                TreeNode root = prOrderBuild(str);
                //输出二叉树中序遍历的结果
                inOrder(root);
                System.out.println();
            }
        }

        private static TreeNode prOrderBuild(String str) {
            char cur = str.charAt(index);
            if (cur == '#') {
                return null;
            }
            TreeNode root = new TreeNode(cur);
            index++;
            //递归处理左子树
            root.left = prOrderBuild(str);
            index++;
            //递归处理右子树
            root.right = prOrderBuild(str);
            return root;
        }

        private static void inOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            //先遍历左子树
            inOrder(root.left);
            //访问根节点
            System.out.print(root.val + " ");
            //最后访问右节点
            inOrder(root.right);
        }
    }
}
